class Solution {
    int ne[50000 + 10];
public:
    int strStr(string haystack, string needle) {
        if(needle.length() == 0) return 0;
        ne[0] = -1;
        for(int i = 1,j = -1;i < needle.length();i++){
            while(j != -1 && needle[i] != needle[j + 1]) j = ne[j];
            if(needle[i] == needle[j + 1]) j ++;
            ne[i] = j;
        }

        for(int i = 0,j = -1;i < haystack.length();i++){
            while(j != -1 && haystack[i] != needle[j + 1]) j = ne[j];
            if(haystack[i] == needle[j + 1]) j++;
            if(j == needle.length() - 1) return i - j;
        }
        return -1;
    }
};